{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子近似优化算法\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概览\n",
    "\n",
    "量子近似优化算法（quantum approximate optimization algorithm, QAOA）是可以在近期的有噪中等规模量子（noisy intermediate-scale quantum, NISQ）设备上运行且具有广泛应用前景的量子算法。QAOA 由 Edward Farhi 等人于 2014 年提出 [1]，其目的是近似地求解组合优化问题（combinatorial optimization problems）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 组合优化问题\n",
    "\n",
    "在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类课题。简单来说，组合优化问题是指问题的所有解是由离散变量组成的，然后在离散的解集中寻找最优解。组合优化问题涉及的范围很广，且常见于实际生活中，例如飞机航线的设计、快递物流路线的规划等。\n",
    "\n",
    "具体来说，一个组合优化问题可以由 $n$ 个比特（bit）和 $m$ 个子句（clause）描述。每个比特是一个二进制变量，其取值为 $0$ 或 $1$，我们用 $z_j$ 表示第 $j$ 个比特的取值。因此，这 $n$ 个比特的取值可以由比特串 $z=z_1z_2\\dots z_n$ 表示。每个子句都是对部分比特的一个限制条件，例如一个子句可以要求第 $2$ 个比特的取值为 $0$，或者可以要求第 $3$ 个比特和第 $5$ 个比特的取值相同，等等。对于第 $j$ 个子句，我们定义一个与之相关的函数\n",
    "\n",
    "$$\n",
    "C_j(z)=\n",
    "\\begin{cases}\n",
    "1 & \\text{如果 $n$ 个比特的取值 $z$ 满足子句 $j$ 表明的条件}\\\\\n",
    "0 & \\text{如果 $n$ 个比特的取值 $z$ 不满足子句 $j$ 表明的条件}\n",
    "\\end{cases}.\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "例如，如果第一个子句要求第二个比特的取值为 0，那么我们有 $C_1(z_10z_3\\dots z_n)=1$ 和 $C_1(z_11z_3\\dots z_n)=0$。\n",
    "\n",
    "由公式（1）中我们对于每个子句定义的函数 $C_j$，我们可以定义该组合优化问题的目标函数（objective function）\n",
    "\n",
    "$$\n",
    "C(z)=\\sum_{j=1}^m w_jC_j(z),\n",
    "\\tag{2}\n",
    "$$\n",
    "\n",
    "其中 $w_j$ 是第 $j$ 个子句的权重（weight）。组合优化问题就是要找到一个取值 $z$ 使得目标函数 $C(z)$ 的值最大，即\n",
    "\n",
    "$$\n",
    "\\underset{z}{\\operatorname{argmax}} C(z).\n",
    "\\tag{3}\n",
    "$$\n",
    "\n",
    "在理论计算机科学中，有一个著名的问题叫作布尔可满足性问题（Boolean satisfiability problem, SAT），它是指对于输入的一组 $n$ 个比特和 $m$ 个子句，判断是否存在一种 $n$ 个比特的取值同时满足所有 $m$ 个子句。而一个与之相关的优化问题叫作最大布尔可满足性问题（MAX-SAT），该问题是要寻找一种 $n$ 个比特的取值以同时满足尽可能多的子句。值得注意的是，上面定义组合优化问题的方式其实就是将其抽象为了 MAX-SAT，更准确地说，是 MAX-SAT 的一个推广版本，即加权 MAX-SAT（weighted MAX-SAT）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 量子近似优化算法\n",
    "\n",
    "在实际生活中，许多组合优化问题都属于 NP 完全（NP-complete）问题甚至是 NP 困难（NP-hard）问题，这意味着计算机很可能无法高效地解决这样的问题。此时，一种替代方案便是寻找这类问题的近似最优解，而这样的任务通常是可以高效完成的。QAOA 就是一个可以寻找到一个组合优化问题的近似最优解的量子算法。\n",
    "\n",
    "### 编码组合优化问题\n",
    "\n",
    "对于上述的一个组合优化问题，有 $n$ 个比特和 $m$ 个子句。QAOA 算法将这个问题转化为了在 $n$ 个量子比特系统上的优化问题，该量子系统的每个计算基态 $|z\\rangle \\in \\{0,1\\}^n$ 对应着原问题中 $n$ 个比特的一种取值 $z$。同时，对于原问题中的第 $j$ 个子句，我们定义一个对角（diagonal）哈密顿量 $H_{C_j}$ 使其满足\n",
    "\n",
    "$$\n",
    "H_{C_j}|z\\rangle = C_j(z)|z\\rangle.\n",
    "\\tag{4}\n",
    "$$\n",
    "\n",
    "具体我们可以通过下式来构造哈密顿量 $H_{C_j}$：\n",
    "\n",
    "$$\n",
    "H_{C_j} = \\sum_{z\\in\\{0,1\\}^n} C_j(z)|z\\rangle\\langle z|.\n",
    "\\tag{5}\n",
    "$$\n",
    "\n",
    "例如，假设满足第 $j$ 个子句的取值有 $z^{(1)}$ 和 $z^{(2)}$，那么我们可以定义\n",
    "\n",
    "$$\n",
    "H_{C_j} = |z^{(1)}\\rangle\\langle z^{(1)}| + |z^{(2)}\\rangle\\langle z^{(2)}|.\n",
    "\\tag{6}\n",
    "$$\n",
    "\n",
    "由此，QAOA 将组合优化问题的目标函数 $C$ 编码成了 $n$ 个量子比特系统上的哈密顿量\n",
    "\n",
    "$$\n",
    "H_C = \\sum_{j=1}^m w_jH_{C_j},\n",
    "\\tag{7}\n",
    "$$\n",
    "\n",
    "并且\n",
    "\n",
    "$$\n",
    "H_C|z\\rangle = \\sum_{j=1}^m w_jH_{C_j}|z\\rangle = \\sum_{j=1}^m w_jC_j(z)|z\\rangle = C(z)|z\\rangle.\n",
    "\\tag{8}\n",
    "$$\n",
    "\n",
    "值得注意的是，假设原问题的一个最优解是 $z_\\text{opt}$，那么我们有\n",
    "\n",
    "$$\n",
    "\\langle z_\\text{opt}|H_C|z_\\text{opt}\\rangle = \\langle z_\\text{opt}|C(z_\\text{opt})|z_\\text{opt}\\rangle = C(z_\\text{opt})\\langle z_\\text{opt}|z_\\text{opt}\\rangle = C(z_\\text{opt}).\n",
    "\\tag{9}\n",
    "$$\n",
    "\n",
    "因此，原组合优化问题的最优解是哈密顿量 $H_C$ 的一个拥有最大本征值（eigenvalue）的本征态（eigenstate）。此外，对于任意量子态 $|\\psi\\rangle$，\n",
    "\n",
    "$$\n",
    "\\langle\\psi|H_C|\\psi\\rangle \\leq C(z_\\text{opt}),\n",
    "\\tag{10}\n",
    "$$\n",
    "\n",
    "且该式取等号当且仅当 $|\\psi\\rangle$ 是几个最优解的叠加态。由式（9）和式（10）可以得到，\n",
    "\n",
    "$$\n",
    "\\max_{|\\psi\\rangle} \\langle\\psi|H_C|\\psi\\rangle = C(z_\\text{opt})，\n",
    "\\tag{11}\n",
    "$$\n",
    "\n",
    "并且寻找原组合优化问题的最优解等同于寻找哈密顿量 $H_C$ 的一个拥有最大本征值的本征态，即寻找一个量子态 $|\\psi\\rangle$ 使得\n",
    "\n",
    "$$\n",
    "H_C|\\psi\\rangle = C(z_\\text{opt})|\\psi\\rangle.\n",
    "\\tag{12}\n",
    "$$\n",
    "\n",
    "找到这样一个量子态 $|\\psi\\rangle$ 后，它很可能并不是一个计算基态，而是几个计算基态的叠加，这其中的每个计算基态都是原组合优化问题的一个最优解。因此，我们对 $|\\psi\\rangle$ 进行计算基上的测量，便能得到原组合优化问题的一个最优解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 寻找近似最优解\n",
    "\n",
    "尽管将要解决的组合优化问题的目标函数编码成一个量子系统的哈密顿量 $H_C$ 较为简单，但想要根据式（11）从偌大的希尔伯特空间中找到代表最优解的量子态 $|\\psi\\rangle$ 并不容易。为了找到这样一个量子态，我们需要借助另一个哈密顿量\n",
    "\n",
    "$$\n",
    "H_B = \\sum_{j=1}^n X_j,\n",
    "\\tag{13}\n",
    "$$\n",
    "\n",
    "其中 $X_j$ 表示作用在第 $j$ 个量子比特上的 Pauli $X$ 门。Pauli $X$ 门的两个本征态分别是 $|+\\rangle$ 和 $|-\\rangle$，它们对应的本征值分别是 $1$ 和 $-1$：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "X|+\\rangle &=\n",
    "\\begin{bmatrix}\n",
    "0&1\\\\1&0\n",
    "\\end{bmatrix}\n",
    "\\frac{1}{\\sqrt{2}}\n",
    "\\begin{bmatrix}\n",
    "1\\\\1\n",
    "\\end{bmatrix}\n",
    "= \\frac{1}{\\sqrt{2}}\n",
    "\\begin{bmatrix}\n",
    "1\\\\1\n",
    "\\end{bmatrix}\n",
    "= |+\\rangle,\\tag{14}\\\\\n",
    "X|-\\rangle &=\n",
    "\\begin{bmatrix}\n",
    "0&1\\\\1&0\n",
    "\\end{bmatrix}\n",
    "\\frac{1}{\\sqrt{2}}\n",
    "\\begin{bmatrix}\n",
    "1\\\\-1\n",
    "\\end{bmatrix}\n",
    "= \\frac{1}{\\sqrt{2}}\n",
    "\\begin{bmatrix}\n",
    "-1\\\\1\n",
    "\\end{bmatrix}\n",
    "= -|-\\rangle.\\tag{15}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "因此，$H_B$ 的拥有最大本征值的本征态为\n",
    "\n",
    "$$\n",
    "|s\\rangle \\equiv \\underbrace{|+\\rangle\\otimes\\cdots\\otimes|+\\rangle}_{\\text{共 $n$ 个 }|+\\rangle} = |+\\rangle^{\\otimes n}.\n",
    "\\tag{16}\n",
    "$$\n",
    "\n",
    "我们将把这个量子态 $|s\\rangle$ 作为算法的初始态。构造出哈密顿量 $H_C$ 和 $H_B$ 后，我们就可以开始寻找原组合优化问题的一个近似最优解了。根据哈密顿量 $H_C$ 和 $H_B$，分别定义酉变换\n",
    "\n",
    "$$\n",
    "U_C(\\gamma) = e^{-i\\gamma H_C}\n",
    "\\tag{17}\n",
    "$$\n",
    "\n",
    "和酉变换\n",
    "\n",
    "$$\n",
    "U_B(\\beta) = e^{-i\\beta H_B},\n",
    "\\tag{18}\n",
    "$$\n",
    "\n",
    "其中 $\\gamma$ 和 $\\beta$ 是实数，为可调节的参数。给定任意一个整数 $p\\geq1$ 以及参数 $\\vec{\\gamma}=(\\gamma_1,\\dots,\\gamma_p)$ 和 $\\vec{\\beta}=(\\beta_1,\\dots,\\beta_p)$，我们定义\n",
    "\n",
    "$$\n",
    "|\\vec{\\gamma},\\vec{\\beta}\\rangle = U_B(\\beta_p)U_C(\\gamma_p)\\cdots U_B(\\beta_1)U_C(\\gamma_1)|s\\rangle.\n",
    "\\tag{19}\n",
    "$$\n",
    "\n",
    "可以看到，整数 $p$ 表示用到的 $U_C,U_B$ 的层数，即分别将 $U_C$ 和 $U_B$ 交替地作用在初始态 $|s\\rangle$ 上 $p$ 次。我们记 $F_p(\\vec{\\gamma},\\vec{\\beta})$ 为哈密顿量 $H_C$ 在式（19）的量子态下的期望值，\n",
    "\n",
    "$$\n",
    "F_p(\\vec{\\gamma},\\vec{\\beta}) = \\langle\\vec{\\gamma},\\vec{\\beta}|H_C|\\vec{\\gamma},\\vec{\\beta}\\rangle.\n",
    "\\tag{20}\n",
    "$$\n",
    "\n",
    "通过调整参数 $\\vec{\\gamma},\\vec{\\beta}$，我们可以得到\n",
    "\n",
    "$$\n",
    "M_p = \\max_{\\vec{\\gamma},\\vec{\\beta}} F_p(\\vec{\\gamma},\\vec{\\beta})\n",
    "\\tag{21}\n",
    "$$\n",
    "\n",
    "作为给定层数 $p$ 下的近似最优解。至此，我们将寻找量子态 $|\\psi\\rangle$ 的问题转变为了搜寻参数 $\\vec{\\gamma},\\vec{\\beta}$ 的问题。值得注意的是，$p$ 层酉变换 $U_C,U_B$ 的表达能力强于 $p-1$ 层的表达能力，因此\n",
    "\n",
    "$$\n",
    "M_p \\geq M_{p-1}.\n",
    "\\tag{22}\n",
    "$$\n",
    "\n",
    "事实上，当 $p$ 足够大时，\n",
    "\n",
    "$$\n",
    "\\lim_{p\\to\\infty} M_p = \\max_z C(z).\n",
    "\\tag{23}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解码量子答案\n",
    "\n",
    "在上一段中，尽管我们将寻找量子态 $|\\psi\\rangle$ 转变为了寻找参数化量子态 $|\\vec{\\gamma},\\vec{\\beta}\\rangle$ 以方便我们的搜索，但同时我们也缩小了搜索的空间，也就是说，在给定层数 $p$ 的情况下，可能并不存在参数 $\\vec{\\gamma},\\vec{\\beta}$ 使得 $F_p(\\vec{\\gamma},\\vec{\\beta}) = C(z_\\text{opt})$。假设参数 $\\vec{\\gamma}^*$ 和 $\\vec{\\beta}^*$ 使得 $F_p$ 最大，即 $F_p(\\vec{\\gamma}^*,\\vec{\\beta}^*) = M_p$，那么在理想情况下量子态 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 包含了最优解的信息。但要注意的是，这里只使用了 $p$ 层，因此很可能 $M_p < C(z_\\text{opt})$。因此，一般情况下 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 只包含了近似最优解的信息。进一步地，我们假设量子态 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 是 $l$ 个计算基态的叠加态，即\n",
    "\n",
    "$$\n",
    "|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle = c_1|z^{(1)}\\rangle + \\cdots + c_l|z^{(l)}\\rangle.\n",
    "\\tag{24}\n",
    "$$\n",
    "\n",
    "通常情况下，一个态 $|z^{(j)}\\rangle$ 在计算基上测量得到的概率 $|c_j|^2$ 越大，意味着其对应的比特串 $z^{(j)}$ 是最优解的可能性越大。那么我们制备 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 并测量，得到一个比特串 $z$ 并计算 $C(z)$ 的值。重复多次这个过程，便能得到一个 $z$ 使得 $C(z)$ 接近甚至超过 $M_p$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 绝热定理\n",
    "\n",
    "为什么可以用上述的方法来构造量子态 $|\\vec{\\gamma},\\vec{\\beta}\\rangle$？ QAOA 试图找到一个优化问题的近似最优解，一个与之类似的算法是量子绝热算法 [2]（quantum adiabatic algorithm, QAA）。但不同的是，QAA 是为了找到优化问题的最优解而非近似最优解。与 QAOA 类似，QAA 将一个优化问题转化为了求一个哈密顿量的基态的问题，并利用绝热定理（adiabatic theorem）对其求解。考虑一个量子系统的哈密顿量\n",
    "\n",
    "$$\n",
    "H(t) = (1-\\frac tT)H_B + \\frac tT H_C,\n",
    "\\tag{25}\n",
    "$$\n",
    "\n",
    "初始时，时间 $t=0$，该系统的哈密顿量为 $H(0) = H_B$。随着时间的流逝，该系统的哈密顿量逐渐由 $H_B$ 变为 $H_C$。当 $t=T$ 时，该系统的哈密顿量变为 $H(T) = H_C$。量子力学中的绝热定理告诉我们，如果初始时该系统处于 $H_B$ 的一个本征态，那么只要时间 $T$ 足够长，当系统的哈密顿量完全演化为 $H_C$ 时，该系统会处于 $H_C$ 的对应能级的本征态。因此，如果初始时该系统处于 $|s\\rangle$，即 $H_B$ 拥有最大本征值的本征态，经过足够长的演化时间 $T$，该系统的量子态会变为 $H_C$ 拥有最大本征值的本征态。[3]\n",
    "\n",
    "一种模拟哈密顿量 $H(t)$ 随着时间 $t$ 演化的方法便是交替地在该量子系统上作用酉变换 $U_C(\\gamma)$ 和 $U_B(\\beta)$，而模拟的精度取决于 $\\gamma,\\beta$ 的取值。另外，为了让系统的演化遵循绝热定理，需要足够长的演化时间，所以要求 $p$ 的取值足够大。因此，结合公式（22）可以推出公式（23）中的结论。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[1] Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. [arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)\n",
    "\n",
    "[2] Farhi, E., Goldstone, J., Gutmann, S. & Sipser, M. Quantum computation by adiabatic evolution. [arXiv:quant-ph/0001106 (2000).](https://arxiv.org/abs/quant-ph/0001106)\n",
    "\n",
    "[3] Duan, R. Quantum Adiabatic Theorem Revisited. [arXiv:2003.03063 (2020).](https://arxiv.org/abs/2003.03063)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
